Efficient Squares and Turing Universality at Temperature 1 with a Unique Negative Glue

摘要

Is Winfree's abstract Tile Assembly Model (aTAM) "powerful?" Well, if certaintiles are required to "cooperate" in order to be able to bind to a growing tileassembly (a.k.a., temperature 2 self-assembly), then Turing universalcomputation and the efficient self-assembly of $N \times N$ squares isachievable in the aTAM (Rotemund and Winfree, STOC 2000). So yes, in acomputational sense, the aTAM is quite powerful! However, if one completelyremoves this cooperativity condition (a.k.a., temperature 1 self-assembly),then the computational "power" of the aTAM (i.e., its ability to support Turinguniversal computation and the efficient self-assembly of $N \times N$ squares)becomes unknown. On the plus side, the aTAM, at temperature 1, isn't onlyTuring universal but also supports the efficient self-assembly $N \times N$squares if self-assembly is allowed to utilize three spatial dimensions (Fu,Schweller and Cook, SODA 2011). We investigate the theoretical "power" of aseemingly simple, restrictive class of tile assembly systems (TASs) in which(1) the absolute value of every glue strength is 1, (2) there's a singlenegative strength glue type and (3) unequal glues can't interact. We call thesethe \emph{restricted glue} TASs (rgTAS). We first show the tile complexity ofproducing an $N \times N$ square with an rgTAS is $O(\frac{\log n}{\log \logn})$. We also prove that rgTASs are Turing universal with a construction thatsimulates an arbitrary Turing machine. Next, we provide results for a variationof the rgTAS class, partially restricted glue TASs, which is similar exceptthat the magnitude of the negative glue's strength can only assumed to be $\ge1$. These results consist of a construction with $O(\log n)$ tile complexityfor building $N \times N$ squares, and one which simulates a Turing machine butwith a greater scaling factor than for the rgTAS construction.